#include <iostream>
#include <vector>
using namespace std;

struct TreeNode
{
public:
    TreeNode(int x)
        :left(nullptr)
        ,right(nullptr)
    {
        val = x;
    }
    int val;
    TreeNode* left;
    TreeNode* right;
};

TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2)
{
    if (t1 == nullptr)
    {
        return t2;
    }
    if (t2 == nullptr)
    {
        return t1;
    }
    TreeNode* ans = new TreeNode(t1->val + t2->val);
    ans->left = mergeTrees(t1->left, t2->left);
    ans->right = mergeTrees(t1->right, t2->right);
    return ans;
}

vector<int> ret;
void dfs(TreeNode* root)
{
    if (root == nullptr)
    {
        return;
    }
    dfs(root->left);
    ret.push_back(root->val);
    dfs(root->right);
}
int main()
{
    TreeNode* t1 = new TreeNode(1);
    TreeNode* t2 = new TreeNode(3);
    TreeNode* t3 = new TreeNode(2);
    TreeNode* t4 = new TreeNode(5);
    t1->left = t2;
    t1->right = t3;
    t2->left = t4;
    
    TreeNode* t5 = new TreeNode(2);
    TreeNode* t6 = new TreeNode(1);
    TreeNode* t7 = new TreeNode(3);
    TreeNode* t8 = new TreeNode(4);
    TreeNode* t9 = new TreeNode(7);
    t5->left = t6;
    t5->right = t7;
    t6->right = t8;
    t7->right = t9;

    TreeNode* ans = mergeTrees(t1, t5);
    dfs(ans);
    for (int i = 0; i < ret.size(); i++)
    {
        cout << ret[i] << " ";
    }
    return 0;
}